The present invention relates to means and methods for reducing the time that is required to search a database, insert records into a database, update records in a database, or delete records from a database.
The ability within a database to quickly insert, update, select, or delete individual records that match a particular criterion is of substantial commercial value. Some database systems offer enhanced speed at the cost of sacrificing the ACID (atomicity, consistency, isolation, durability) properties of the database system. The ability to offer high performance while still maintaining the integrity of these properties is greatly desired.
One way to improve the response time of a request to a database is to partition the database table into smaller components (“partitions”) by distributing the records, or rows, to different database processes. Each partition is located in a separate process, or a distinct virtual address space managed by the host operating system. The partitions may be on either separate database servers or the same database server. Each individual partition is referred to as a database “shard.” An advantage of this approach is that the number of rows in each table is reduced. The use of shards (“sharding”) reduces the index size, reduces contention on database resources, and allows for improved performance. Depending on the method used to partition the database it may be possible to execute a request on a limited subset of the shards when it is known that the limited subset would contain all of the request responses.
However, sharding suffers a penalty in that data must be explicitly communicated between shards when operations occur that require communication between shards such as a join, ordering with a limit, or some other aggregation.
While sharding may reduce database response time, there is additional overhead in maintaining a distributed partition map for the database shards and creating the communication structures that are necessary to distribute the requests and consolidate responses. In common practice, much of this overhead is managed outside the database in the application layer of software, since the database is itself sharded and has no central repository to manage this state. This additional complexity makes sharding less usable and therefore less desirable to application developers.
When a database is sharded, the communication overhead can be a significant cost. Before intermediate results from each shard can be reduced to a final result set, the intermediates must be communicated to a central process that aggregates the intermediates and produces the final result set. Often during the aggregation process many of the intermediates are discarded. Those intermediate results which do not actually qualify as part of the final result set use up valuable bandwidth in communication channels which can be quite expensive.
It is therefore desirable to improve the response time and decrease the maintenance overhead associated with database requests.